Digital processing circuitry, and apparatus including such circuitry, is pervasive in modern society. The use of digital processing circuitry is advantageous as repetitive functions can be carried out at rates dramatically more quickly than that which can be performed manually. And, because of the rapid speed at which the operations can be performed, activities previously considered impractical can be readily implemented. The use of digital processing circuitry advantageously permits, e.g., the processing of large amounts of data. For instance, in a computer system, data is transferred between peripheral devices, and between peripheral devices and a CPU (central processing unit). In such processing of data, data is read from, or written to, data storage locations in successive read and write operations.
The data is stored in the form of binary bits and, when the reading or writing the data from or to the data storage locations, the binary bits are transferred. During transfer of the data, errors are sometimes introduced as a result of, e.g., channel distortion or noise. Errors can also be introduced by defects of the data storage locations at which the data is stored. The errors in the data must typically be corrected to ensure data integrity. To facilitate error correction of the data, encoding techniques are sometimes utilized to encode data prior to its transfer. Once transferred, the encoded data is thereafter decoded to recreate the values of the data, prior to its encoding and transfer. By encoding the data, redundancies are introduced upon the data. Such redundancies increase the likelihood that the data can be recovered even if errors are introduced into the data during its transfer.
Various encoding schemes have been developed and are commonly utilized in digital processing and communication devices. Reed-Solomon coding is exemplary of an encoding scheme sometimes utilized to encode digital data.
Industry-wide standards have been set forth for coding and error correction schemes to provide for intercompatibility of products and devices constructed by different manufacturers. Standards have been set forth, for instance, for the encoding of data stored on optical storage devices, such as CD-ROM storage devices. In such storage devices, data is stored in the form of blocks of data; for instance, blocks of data are sometimes formed in two-dimensional arrays. Such blocks include CRC (cyclic redundancy code) bits interleaved together with an ECC (error correction code) used for error correction operations and data integrity testing.
When the block of data is transferred, ECC-error correcting operations are performed upon the block of data to correct for errors introduced upon the data of any of the locations of the two-dimensional array. Once corrected, CRC calculations are performed upon the data to check for the correctness of the error corrections performed by the ECC-error correcting operations. If the errors have been adequately corrected, a CRC remainder, calculated during the CRC calculations is of a zero value.
In one conventional manner by which to perform CRC calculations, the block of data, along with the CRC bits, are stored in a chip memory. Error corrections are performed upon the appropriate locations of the data, the CRC remainder is calculated over the entire block of corrected data, and the data is then stored in a buffer memory.
In another manner, the data is first stored in a buffer memory, error correction is performed upon the data in the buffer memory, and, thereafter, the CRC remainder is calculated by reading the entire block of data from the buffer memory.
And, in another manner, the array of data is stored in a buffer memory, the CRC remainder on the uncorrected data is calculated as it is being stored to the buffer memory, the error locations and magnitudes of errors detected in the block of data are calculated, error corrections are performed in the buffer memory, and then the CRC remainder is adjusted by cycling through a "dummy" block of data. The "dummy" block of data is formed of zero values except for the error magnitudes at the locations of the array at which errors are detected.
All such conventional manners by which to perform error correction operations and CRC calculations require disadvantageously large amounts of storage space in a relatively expensive storage medium. Also, a large amount of buffer memory bandwidth utilization is required, large time delays are required for the processing of the error corrections and CRC calculations, and, complicated sequential ordering is required for such operations.
A manner by which to perform CRC calculations in a reduced amount of time, requiring less processing, and less bandwidth utilization would be advantageous.
It is in light of this background information related to ECC and CRC calculations that the significant improvements of the present invention have evolved.